% select_spill_plan.m
% 封装了SPILL受害者选择的完整决策逻辑。
%
% @输入:
%   graph (struct): 计算图结构体，用于查找节点信息。
%   active_buffers (Map): 当前已分配的buffer
%   manager (struct): 当前缓存层的管理器状态
%   size_needed (numeric): 需要分配的内存大小
%   type_code (int): 缓存类型
%   schedule (vector): 当前的完整调度序列
%   step (int): 当前的调度步骤
%   min_farthest_use_threshold (numeric): 最小未来使用距离阈值
%   w_use (numeric): farthest_use 的权重
%   w_vol (numeric): volume 的权重
%   w_vic (numeric): victims 数量的权重
% @输出:
%   best_plan (struct): 计算出的最优SPILL方案
%   success (boolean): 是否成功找到了方案
% *** 已修改: 增加Spill策略参数 ***
function [best_plan, success] = select_spill_plan(graph, active_buffers, manager, size_needed, type_code, schedule, step, min_farthest_use_threshold, w_use, w_vol, w_vic)
    % --- 1. 计算所有潜在牺牲品的信息 ---
    all_candidate_info_map = containers.Map('KeyType', 'int32', 'ValueType', 'any');
    active_keys = cell2mat(keys(active_buffers));
    for k_idx = 1:length(active_keys)
        candidate_buf_id = active_keys(k_idx);
        buffer_info = active_buffers(candidate_buf_id);
        candidate_type_code = buffer_info(1);
        candidate_size = buffer_info(3);
        if candidate_type_code ~= type_code, continue; end
        
        farthest_use = 0;
        for future_step = (step + 1):length(schedule)
            future_node = graph.nodes(schedule(future_step));
            found = false;
            if ~isempty(future_node.bufs) && ismember(candidate_buf_id, future_node.bufs)
                found = true;
            end
            if ~found && ~isempty(future_node.buf_id) && future_node.buf_id == candidate_buf_id
                found = true;
            end
            if found
                farthest_use = future_step;
                break;
            end
        end
        if farthest_use == 0, farthest_use = length(schedule) + 2; end
        all_candidate_info_map(candidate_buf_id) = {farthest_use, candidate_size};
    end
    % --- 2. 根据阈值筛选牺牲品，并确定是否启用回退 ---
    filtered_candidate_info_map = containers.Map('KeyType', 'int32', 'ValueType', 'any');
    candidate_keys = keys(all_candidate_info_map);
    for i = 1:length(candidate_keys)
        k = candidate_keys{i};
        info = all_candidate_info_map(k);
        if info{1} > min_farthest_use_threshold
            filtered_candidate_info_map(k) = info;
        end
    end
    
    use_fallback = isempty(filtered_candidate_info_map);
    if use_fallback
        candidate_info_map = all_candidate_info_map; % 回退: 使用所有候选
    else
        candidate_info_map = filtered_candidate_info_map; % 正常: 使用筛选后的候选
    end
    % --- 3. 生成所有可能的 Spill 计划 ---
    anchor_points = unique([[manager.free_blocks.start], [manager.allocated_blocks.start]]);
    all_plans = [];
    for anchor_addr = anchor_points
        window_start = anchor_addr;
        window_end = window_start + size_needed;
        if window_end > manager.capacity, continue; end
        
        current_plan = struct('victim_ids', [], 'cost_future_use', inf, 'cost_volume', 0, 'cost_victims', 0, 'start_address', anchor_addr, 'victim_details', containers.Map('KeyType', 'int32', 'ValueType', 'any'));
        for blk_idx = 1:length(manager.allocated_blocks)
            alloc_block = manager.allocated_blocks(blk_idx);
            if alloc_block.start < window_end && (alloc_block.start + alloc_block.size) > window_start
                if isKey(candidate_info_map, alloc_block.buf_id)
                    current_plan.victim_ids = [current_plan.victim_ids, alloc_block.buf_id];
                end
            end
        end
        
        if ~isempty(current_plan.victim_ids)
            min_future_use = inf;
            total_volume = 0;
            for v_id = current_plan.victim_ids
                info = candidate_info_map(v_id);
                min_future_use = min(min_future_use, info{1});
                total_volume = total_volume + info{2};
                current_plan.victim_details(v_id) = info;
            end
            current_plan.cost_future_use = min_future_use;
            current_plan.cost_volume = total_volume;
            current_plan.cost_victims = length(current_plan.victim_ids);
            all_plans = [all_plans; current_plan];
        end
    end
    if isempty(all_plans)
        best_plan = [];
        success = false;
        return;
    end
    
    % --- 4. 根据模式选择最佳计划 ---
    if use_fallback
        % --- 回退逻辑: 多级排序 ---
        if length(all_plans) == 1
            best_plan = all_plans(1);
            success = true;
            return;
        end
        costs = vertcat(all_plans.cost_future_use);
        volumes = vertcat(all_plans.cost_volume);
        victims = vertcat(all_plans.cost_victims);
        [~, sorted_indices] = sortrows([-costs, volumes, victims], [1, 2, 3]);
        best_plan = all_plans(sorted_indices(1));
    else
        % --- 主要逻辑: 加权求和 ---
        if length(all_plans) == 1
            best_plan = all_plans(1);
            success = true;
            return;
        end
        
        % 提取指标
        costs = vertcat(all_plans.cost_future_use);
        volumes = vertcat(all_plans.cost_volume);
        victims = vertcat(all_plans.cost_victims);
        
        % 归一化
        min_c = min(costs); max_c = max(costs);
        min_v = min(volumes); max_v = max(volumes);
        min_vic = min(victims); max_vic = max(victims);
        
        norm_costs = (costs - min_c) ./ max(1, (max_c - min_c));
        norm_vols = (volumes - min_v) ./ max(1, (max_v - min_v));
        norm_vics = (victims - min_vic) ./ max(1, (max_vic - min_vic));
        
        % 计算加权总成本
        min_total_cost = inf;
        best_plan_idx = -1;
        for i = 1:length(all_plans)
            total_cost = w_use * (1 - norm_costs(i)) + w_vol * norm_vols(i) + w_vic * norm_vics(i);
            if total_cost < min_total_cost
                min_total_cost = total_cost;
                best_plan_idx = i;
            end
        end
        best_plan = all_plans(best_plan_idx);
    end
    success = true;
end